package com.mlh.dp.old;

// 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
// 'A' -> "1"
// 'B' -> "2"
// ...
// 'Z' -> "26"
// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
// "AAJF" ，将消息分组为 (1 1 10 6)
// "KJF" ，将消息分组为 (11 10 6)
// 注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
// 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
// 题目数据保证答案肯定是一个 32 位 的整数。
//
// 输入：s = "12"
// 输出：2
// 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

import java.util.Arrays;

public class NumDecodings {
    public static void main(String[] args) {
        System.out.println(method1("2611055971756562"));
    }

    //看了题解写出来的
    //这题状态转移方程很好推
    //但是边界条件比较难确定  其主要原因是对题意的不理解
    //这是第一版代码  很多地方可以进行优化  空间优化  返回优化等等
    public static int method1(String s) {
        char[] nums = s.toCharArray();
        int[] dp=new int[nums.length];
        if(nums[0]=='0'){
            return 0;
        }
        dp[0]=1;
        //状态转移公式
        //主要就是判断两个数字合起来是否在10-26之间
        for(int i=1;i<nums.length;i++){
            if(Character.getNumericValue(nums[i])!=0){
                dp[i]+=dp[i-1];
            }
            if(Character.getNumericValue(nums[i-1])!=0
                    &&Character.getNumericValue(nums[i-1])*10+Character.getNumericValue(nums[i])<=26){
                if(i==1){
                    if(Character.getNumericValue(nums[i])==0){
                        dp[i]=1;
                    }else{
                        dp[i]=2;
                    }
                }else{
                    dp[i]+=dp[i-2];
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[nums.length-1];
    }

    //题解方法
    //自己的问题是在于对题目要求考察不清楚
    //15066 这种字符串返回值是0  也就是说字符串如果没办法被正确解码的话 返回值都为0
    public static int method2(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != '0') {
                f[i] += f[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }

}
